package com.wz.leetcode.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author : Wang Zhen.
 * @Date : Created in 10:27 2022/9/25
 * @Description :
 * @Modified By   :
 * @Version :
 */
public class N0015_3sum {
    public static List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        if (null == nums || n < 3) {
            return null;
        }
        // 依次将数组的第一个元素作为target，然后在剩下的数组寻找两个之和为target的数
        List<List<Integer>> result = new ArrayList<>();
        // 排序是为了去重方便
        Arrays.sort(nums);
        // 三个数，确定第一个数i，然后利用双指针解决后面两个数j k
        for (int i = 0; i < n - 2;)  {
            // 双指针法
            int j = i + 1;
            int k = n - 1;
            int target = - nums[i];
            while (j < k) {
                while (j < k && nums[j] + nums[k] > target) {
                    k--;
                }
                // 这里不能少了j < k，否则当j == k时，会一个位置取两次
                if (j < k && nums[j] + nums[k] == target) {
                    result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
                }
                j++;
                // 跳过重复的j
                while (j < k && nums[j] == nums[j - 1]) {
                    j++;
                }
            }
            i++;
            while (i < n - 2 && nums[i] == nums[i - 1]) {
                i++;
            }
        }
        return result;
    }


    public static List<List<Integer>> threeSum2(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue;
            }
            int k = n - 1;
            int target = -nums[i];
            for (int j = i + 1; j < n - 1; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                while (j < k && nums[j] + nums[k] > target) {
                    --k;
                }
                if (j == k) {
                    break;
                }
                if (nums[j] + nums[k] == target) {
                    ans.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k])));
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(threeSum2(new int[]{-1,0,1,2,-1,-4}));
        System.out.println(threeSum2(new int[]{0, 1, 1}));
    }
}
